To solve the user similarity between trajectories formed by mobility data, an algorithm based on Location Sequence Generalized Suffix Tree (LSGST) was proposed. First, the location sequence was extracted from mobility data. At the same time the location sequence was mapped to a string. The transformation from the processing of location sequence to the processing of string was completed. Then the location sequence generalized suffix tree between different users was constructed. The similarity was calculated in detail from the number of similar positions, longest common subsequence and the frequent common position sequence. The theoretical analysis and simulation results show that the proposed algorithm has ideal effect in terms of similarity measure. Besides, compared to the ordinary construction method, the proposed algorithm has low time complexity. In the comparison with dynamic programming and naive string-matching, the proposed algorithm has higher efficiency when searching for the longest common sub-string and frequent public position sequence. The experimental results indicate that the LSGST can measure the similarity effectively, meanwhile reduces the trajectory data when searching for the measurement index, and has better performance in time complexity.